class Solution(object):
    def wordPatternMatch(self, pattern, s):
        """
        :type pattern: str
        :type s: str
        :rtype: bool
        """

        n = len(pattern)
        m = len(s)
        if n > m:
            return False
        d1 = {}
        d2 = {}

        def search(i, j):
            if pattern[i] not in d1:
                if i != n - 1:
                    for k in range(j + 1, m - (n - 1 - i) + 1):
                        d1[pattern[i]] = s[j: k]
                        if s[j: k] not in d2:
                            d2[s[j: k]] = pattern[i]
                            flag = search(i + 1, k)
                            d2.pop(s[j: k])
                            if flag:
                                d1.pop(pattern[i])
                                return True
                    d1.pop(pattern[i])
                    return False
                else:
                    if s[j: m] not in d2:
                        return True
                    else:
                        return False
            else:
                if i != n - 1:
                    for k in range(j + 1, m - (n - 1 - i) + 1):
                        if d1[pattern[i]] == s[j: k]:
                            flag = search(i + 1, k)
                            if flag:
                                return True
                            else:
                                return False
                    return False
                else:
                    if d1[pattern[i]] == s[j: m]:
                        return True
                    else:
                        return False
        return search(0, 0)


data = Solution()
pattern = "abab"
s = "scsc"
print(data.wordPatternMatch(pattern, s))
pattern = "aaaa"
s = "asdasdasdasd"
print(data.wordPatternMatch(pattern, s))
pattern = "abab"
s = "redblueredblue"
print(data.wordPatternMatch(pattern, s))
pattern = "aabb"
s = "xyzabcxzyabc"
print(data.wordPatternMatch(pattern, s))
